
/**
 * 
 * RBTree
 * 
 * An implementation of a Red Black Tree
 * 
 * invariant: isValid()
 */

public class RBTree {

	private Node root;
	private Node nil;
	private int blackDepth;

	/**
	 * class constructor
	 * 
	 * precondition: true ;
	 * postcondition: empty();
	 */
	public RBTree() {
		nil = new Node();
		nil.isRed = false;
		nil.item = "nil";
		root = nil;
	}

	/**
	 * class Node represents a red-black-tree node
	 * 
	 * 
	 */
	public class Node {
		int key;
		String item;
		boolean isRed;
		Node papa;
		Node rChild;
		Node lChild;

		// for debug
		public String toString() {
			return Integer.toString(key);
		}
	}

	/**
	 * public boolean empty()
	 * 
	 * returns true if and only if the tree is empty
	 * 
	 * preconditions: true ; postconditions: ($ret==true) iff (size()==0);
	 */
	public boolean empty() {
		return root == nil;
	}

	/**
	 * public String search(int k)
	 * 
	 * returns the string with key k if such a string exists, otherwise return
	 * null
	 * 
	 * preconditions: true ; postconditions: if 'this' contains a node n with key k
	 * then $ret==n.item, otherwise $ret==null
	 */
	public String search(int k) {
		Node found = iterSearch(root, k);
		if (found != nil) {
			return found.item;
		}
		return null;
	}

	/**
	 * search for a Node with key k in the subTree rooted in x.
	 * returns the node if exist in the subtree rooted in root, or nil otherwise.
	 *
	 * precondition: root!=null ;
	 * postcondition: if (there's a node with key searchKey that is descendant from root) 
	 * then ($ret.key==searchKey)
	 * else  ($ret==nil)
	 * 
	 */
	private Node iterSearch(Node root, int searchKey) {
		while (root != nil & searchKey != root.key) {
			if (searchKey < root.key) {
				root = root.lChild;
			} else {
				root = root.rChild;
			}
		}
		return root;
	}

	/**
	 * public void insert(int k, String S)
	 * 
	 * inserts the element (k,S) into the binary tree
	 * 
	 * preconditions: true ;
	 * postconditions: if before entering the method it holds that: (search(k)==null) then after it returns: (search(k)==S && size() increment), else search(k) and size() doesn't change.
	 */
	public void insert(int k, String S) {
		if (search(k) != null) {
			return;
		}
		Node newNode = new Node();
		newNode.key = k;
		newNode.item = S;
		Node newNodePapa = nil;
		Node insertPlace = root;
		while (insertPlace != nil) {
			newNodePapa = insertPlace;
			if (newNode.key < insertPlace.key) {
				insertPlace = insertPlace.lChild;
			} else {
				insertPlace = insertPlace.rChild;
			}
		}
		newNode.papa = newNodePapa;
		if (newNodePapa == nil) {
			root = newNode;
		} else if (newNode.key < newNodePapa.key) {
			newNodePapa.lChild = newNode;
		} else {
			newNodePapa.rChild = newNode;
		}
		newNode.lChild = nil;
		newNode.rChild = nil;
		newNode.isRed = true;
		insertFixup(newNode);
	}

	/**
	 * fix the black and red rules after insert of node 'fixupSource'
	 * 
	 * precondition: fixupSource!=null && search(fixupSource.key)!=null && fixupSource.isRed=true && fixupSource is a new node in tree && !isValid()
	 * postcondition: this method will restore the class invariant.
	 * 
	 */
	private void insertFixup(Node fixupSource) {
		Node fixupSourceUncle;
		while (fixupSource.papa.isRed) {
			if (fixupSource.papa == fixupSource.papa.papa.lChild) {
				fixupSourceUncle = fixupSource.papa.papa.rChild;
				if (fixupSourceUncle.isRed) {
					fixupSource.papa.isRed = false;
					fixupSourceUncle.isRed = false;
					fixupSource.papa.papa.isRed = true;
					fixupSource = fixupSource.papa.papa;
				} else {
					if (fixupSource == fixupSource.papa.rChild) {
						fixupSource = fixupSource.papa;
						leftRotate(fixupSource);
					}
					fixupSource.papa.isRed = false;
					fixupSource.papa.papa.isRed = true;
					rightRotate(fixupSource.papa.papa);
				}
			} else {
				fixupSourceUncle = fixupSource.papa.papa.lChild;
				if (fixupSourceUncle.isRed) {
					fixupSource.papa.isRed = false;
					fixupSourceUncle.isRed = false;
					fixupSource.papa.papa.isRed = true;
					fixupSource = fixupSource.papa.papa;
				} else {
					if (fixupSource == fixupSource.papa.lChild) {
						fixupSource = fixupSource.papa;
						rightRotate(fixupSource);
					}
					fixupSource.papa.isRed = false;
					fixupSource.papa.papa.isRed = true;
					leftRotate(fixupSource.papa.papa);
				}

			}
		}
		root.isRed = false;
	}

	/**
	 * public void delete(int k)
	 * 
	 * deletes the element with key k from the tree. if the tree doesn't contain
	 * an element with key k, does nothing
	 * 
	 * preconditions: true ; 
	 * postconditions: search(k)==null && if before execution it holds that (search(k)=!null) then size() decrease by 1, and not otherwise;  
	 */
	public void delete(int k) {
		Node deleteNode = iterSearch(root, k);
		if (deleteNode == nil) {
			return;
		}
		Node y = deleteNode;
		Node x;
		boolean yWasRed = y.isRed;
		if (deleteNode.lChild == nil) {
			x = deleteNode.rChild;
			transplant(deleteNode, deleteNode.rChild);
		} else if (deleteNode.rChild == nil) {
			x = deleteNode.lChild;
			transplant(deleteNode, deleteNode.lChild);
		} else {
			y = treeMin(deleteNode.rChild);
			yWasRed = y.isRed;
			x = y.rChild;
			if (y.papa == deleteNode) {
				x.papa = y;
			} else {
				transplant(y, y.rChild);
				y.rChild = deleteNode.rChild;
				y.rChild.papa = y;
			}
			transplant(deleteNode, y);
			y.lChild = deleteNode.lChild;
			y.lChild.papa = y;
			y.isRed = deleteNode.isRed;
		}
		if (yWasRed == false) {
			deleteFixup(x);
		}

	}

	/**
	 * transplant the sub tree which root is newSubTree instead of the sub tree which
	 * root is replacedSubTree 
	 * 
	 * precondition: replacedSubTree!=null && newSubTree!=null;  
	 * postcondition: replacedSubTree is replaced by newSubTree. the invariant doens't necessarily holds! - after use its should be corrected
	 */
	private void transplant(Node replacedSubTree, Node newSubTree) {
		if (replacedSubTree.papa == nil) {
			root = newSubTree;

		} else if (replacedSubTree == replacedSubTree.papa.lChild) {
			replacedSubTree.papa.lChild = newSubTree;
		} else {
			replacedSubTree.papa.rChild = newSubTree;
		}
		newSubTree.papa = replacedSubTree.papa;

	}

	/**
	 * fix the black and red rules after deletion of 'fixupSource.papa'
	 * 
	 * precondition: fixupSource!=null && search(fixupSource.key)!=null && fixupSource.papa was just deleted && !isValid()
	 * postcondition: this method will restore the class invariant.
	 * 
	 */
	private void deleteFixup(Node fixupSource) {
		Node uncle;
		while (fixupSource != root && fixupSource.isRed == false) {
			if (fixupSource == fixupSource.papa.lChild) {
				uncle = fixupSource.papa.rChild;
				if (uncle.isRed == true) {
					uncle.isRed = false; // case 1
					uncle.papa.isRed = true; // case 1
					leftRotate(fixupSource.papa); // case 1
					uncle = fixupSource.papa.rChild; // case 1
				}
				if (uncle.lChild.isRed == false && uncle.rChild.isRed == false) {
					uncle.isRed = true; // case 2
					fixupSource = fixupSource.papa;
				} else {
					if (uncle.rChild.isRed == false) {
						uncle.lChild.isRed = false; // case 3
						uncle.isRed = true; // case 3
						rightRotate(uncle); // case 3
						uncle = fixupSource.papa.rChild; // case 3
					}
					uncle.isRed = fixupSource.papa.isRed; // case 4
					fixupSource.papa.isRed = false; // case 4
					uncle.rChild.isRed = false; // case 4
					leftRotate(fixupSource.papa); // case 4
					fixupSource = root;
				}
			} else {
				uncle = fixupSource.papa.lChild;
				if (uncle.isRed == true) {
					uncle.isRed = false; // case 1
					uncle.papa.isRed = true; // case 1
					rightRotate(fixupSource.papa); // case 1
					uncle = fixupSource.papa.lChild; // case 1
				}
				if (uncle.rChild.isRed == false && uncle.lChild.isRed == false) {
					uncle.isRed = true; // case 2
					fixupSource = fixupSource.papa;
				} else {
					if (uncle.lChild.isRed == false) {
						uncle.rChild.isRed = false; // case 3
						uncle.isRed = true; // case 3
						leftRotate(uncle); // case 3
						uncle = fixupSource.papa.lChild; // case 3
					}
					uncle.isRed = fixupSource.papa.isRed; // case 4
					fixupSource.papa.isRed = false; // case 4
					uncle.lChild.isRed = false; // case 4
					rightRotate(fixupSource.papa); // case 4
					fixupSource = root;
				}
			}
		}
		fixupSource.isRed = false;
	}

	/**
	 * @pre: nodePapa.lChild != null && nodePapa != nil , a root of an unbalanced black deep sub tree
	 * 
	 * @post: balanced black deep sub tree
	 */
	private void rightRotate(Node nodePapa) {
		Node nodeBrother = nodePapa.lChild;
		nodePapa.lChild = nodeBrother.rChild;
		if (nodeBrother.rChild != nil) {
			nodeBrother.rChild.papa = nodePapa;
		}
		nodeBrother.papa = nodePapa.papa;
		if (nodePapa.papa == nil) {
			root = nodeBrother;
		} else if (nodePapa == nodePapa.papa.rChild) {
			nodePapa.papa.rChild = nodeBrother;
		} else {
			nodePapa.papa.lChild = nodeBrother;
		}
		nodeBrother.rChild = nodePapa;
		nodePapa.papa = nodeBrother;

	}

	/**
	 * nodePapa.rChild != null && nodePapa != nil , a root of an unbalanced black deep sub tree
	 * 
	 * @post: balanced black deep sub tree
	 */
	private void leftRotate(Node nodePapa) {
		Node nodeBrother = nodePapa.rChild;
		nodePapa.rChild = nodeBrother.lChild;
		if (nodeBrother.lChild != nil) {
			nodeBrother.lChild.papa = nodePapa;
		}
		nodeBrother.papa = nodePapa.papa;
		if (nodePapa.papa == nil) {
			root = nodeBrother;
		} else if (nodePapa == nodePapa.papa.lChild) {
			nodePapa.papa.lChild = nodeBrother;
		} else {
			nodePapa.papa.rChild = nodeBrother;
		}
		nodeBrother.lChild = nodePapa;
		nodePapa.papa = nodeBrother;
	}

	/**
	 * return the Min Node in the sub tree that subTreeRoot is its root node
	 * 
	 * precondition: x!=null && x!=nil 
	 * postcondition: @ret== the least key descendant of subTreeRoot
	 */
	private Node treeMin(Node subTreeRoot) {
		while (subTreeRoot.lChild != nil) {
			subTreeRoot = subTreeRoot.lChild;
		}
		return subTreeRoot;
	}


	/**
	 * public int successor(int k)
	 * 
	 * returns the successor key of k, if k is not the maximum key
	 * 
	 * preconditions: search(k)!=null && there exist k1>k such that
	 * search(k1)!=null; 
	 * postconditions: search($ret)!=null && $ret>k && $ret is
	 * the minimum of the group satisfying the two previous conditions
	 */
	public int successor(int k) {
		Node x = iterSearch(root, k);
		if (x.rChild != nil) {
			return treeMin(x.rChild).key;
		}
		Node y = x.papa;
		while (y != nil && x == y.rChild) {
			x = y;
			y = y.papa;
		}
		return y.key;
	}

	/**
	 * return the Node with the max key in the sub tree that subTreeRoot is its
	 * root node
	 * 
	 * precondition: x!=null && x!=nil;
	 * postcondition: @ret== the max key descendant of subTreeRoot
	 */
	private Node treeMax(Node subTreeRoot) {
		while (subTreeRoot.rChild != nil) {
			subTreeRoot = subTreeRoot.rChild;
		}
		return subTreeRoot;
	}

	/**
	 * public int predecessor(int k)
	 * 
	 * returns the predecessor key of k, if k is not the minimum key
	 * 
	 * preconditions: search(k)!=null && there exist k1<k such that
	 * search(k1)!=null; postconditions: search($ret)!=null && $ret<k && $ret is
	 * the maximum of the group satisfying the two previous conditions
	 */
	public int predecessor(int k) {
		Node x = iterSearch(root, k);
		if (x.lChild != nil) {
			return treeMax(x.lChild).key;
		}
		Node y = x.papa;
		while (y != nil && x == y.lChild) {
			x = y;
			y = y.papa;
		}
		return y.key;
	}

	/**
	 * used to  check if this tree is a valid binary search tree
	 * 
	 * precondition: treeRoot!=null && min<max
	 * postcondition: return true iff all the keys of the descendant of treeRoot (+its own) are between 'min' and 'max' 
	 * 
	 */
	private boolean isBinarySearchTree(Node treeRoot, int min, int max) {
		if (treeRoot==nil){return true;}
		return treeRoot.key > min && treeRoot.key < max
				&& isBinarySearchTree(treeRoot.lChild, min, treeRoot.key)
				&& isBinarySearchTree(treeRoot.rChild, treeRoot.key, max);
	}

	/**
	 * public boolean isValid()
	 * 
	 * precondition: true;
	 * postconditions: Returns true if and only if the tree is a valid red-black
	 * tree. I.e., the tree is a valid search tree, every object is either red
	 * or black, obey the red and black rule, and root and the external  leafs not red.
	 */
	public boolean isValid() {
		blackDepth = -1;
		if (root.isRed) {
			return false;
		}
		return checkRedBlackRules(root, 0) && isBinarySearchTree(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
	}

	/**
	 * precondition: member!=null && counter is the distance between the root node and 'member' measured in no. of arches
	 * postconditions: Returns true if and only if the sub tree which root is 'member' obey the red rule,
	 * and all leaves in the subtree which root is member obey the black rule 
	 */
	private boolean checkRedBlackRules(Node member, int counter) {
		if (member == nil) {
			if (blackDepth == -1) {
				blackDepth = counter;
			}
			if (counter == blackDepth) {
				return true;
			} else {
				return false;
			}
		} else {
			if (member.lChild != nil) {
				if (member.isRed && member.lChild.isRed) {
					return false;
				}
			}
			if (member.rChild != nil) {
				if (member.isRed && member.rChild.isRed) {
					return false;
				}
			}
			if (!member.isRed) {
				counter++;
			}
			return checkRedBlackRules(member.lChild, counter)
					& checkRedBlackRules(member.rChild, counter);
		}
	}

	/**
	 * public int maxDepth()
	 * 
	 * returns the maximum depth of a node in a non-empty tree.
	 * 
	 * preconditions: !empty(); postconditions: $ret is the maximum number of
	 * arches between a node in the tree (including outer leaves) and the root
	 * node.
	 */
	public int maxDepth() {

		return helperMaxDepth(root);
	}

	/**
	 * returns the max distance between a node that is a descendant of 'subTreeRoot'
	 * 
	 * precondition: subTreeRoot!=null;
	 * postcondition: $ret==the max number of arches between 'subTreeRoot' and a descendant of it (including outer leaves). 
	 *                 
	 */
	private int helperMaxDepth(Node subTreeRoot) {
		if (subTreeRoot == nil) {
			return 0;
		}
		return 1 + Math.max(helperMaxDepth(subTreeRoot.lChild),
				helperMaxDepth(subTreeRoot.rChild));
	}

	/**
	 * public int size()
	 * 
	 * returns the number of elements in the tree (excluding outer leaves)
	 * 
	 * preconditions: true;
	 * postconditions: $ret is the number of elements in the
	 * tree (not including outer leaves)
	 */
	public int size() {
		return sizeSubTree(root);
	}

	/**
	 * returns the number of elements descendant from 'subTreeRoot'(excluding outer leaves)
	 * 
	 * precondition: subTreeRoot!=null;
	 * postcondition: $ret== the number of elements in the subtree (not including outer
	 *         leaves)
	 */
	private int sizeSubTree(Node subTreeRoot) {
		if (subTreeRoot == nil) {
			return 0;
		}
		return 1 + sizeSubTree(subTreeRoot.rChild)
				+ sizeSubTree(subTreeRoot.lChild);
	}

}
